/*
 * @Author: szx
 * @Date: 2022-02-11 15:04:18
 * @LastEditTime: 2022-02-11 15:13:59
 * @Description:
 * @FilePath: \leetcode\1400-1499\1447\1447.js
 */
/**
 * @param {number} n
 * @return {string[]}
 */
var simplifiedFractions = function (n) {
    const ans = [];
    // 遍历分母
    for (let denominator = 2; denominator <= n; ++denominator) {
        // 遍历分子
        for (let numerator = 1; numerator < denominator; ++numerator) {
            // 求出最大公约数，如果是1，那么就是最简的了
            if (gcd(numerator, denominator) == 1) {
                ans.push(numerator + '/' + denominator);
            }
        }
    }
    return ans;
};
// 辗转相除法
const gcd = (a, b) => {
    if (b === 0) return a;
    return gcd(b, a % b);
};
